#include <bits/stdc++.h>
using namespace std;

// 定义边的结构体，方便后续处理和可视化
struct Edge {
    int from;
    int to;
    int weight;
    int id; // 边的唯一标识符，用于跟踪使用过的边

    Edge(int f, int t, int w, int i) : from(f), to(t), weight(w), id(i) {}
};

// 图的类封装
class Graph {
private:
    int nodeCount;
    vector<vector<Edge>> adjList;
    vector<Edge> edges; // 存储所有边，用于后续处理

public:
    Graph(int n) : nodeCount(n), adjList(n + 1) {} // 节点编号从1开始

    // 添加边，同时分配唯一ID
    void addEdge(int from, int to, int weight, int id) {
        Edge e1(from, to, weight, id);
        Edge e2(to, from, weight, id); // 无向图，添加双向边
        adjList[from].push_back(e1);
        adjList[to].push_back(e2);
        edges.push_back(e1); // 只存储一次
    }

    // 获取邻接表
    const vector<vector<Edge>>& getAdjList() const {
        return adjList;
    }

    // 获取所有边
    const vector<Edge>& getAllEdges() const {
        return edges;
    }

    // 获取节点数量
    int getNodeCount() const {
        return nodeCount;
    }

    // 打印图结构
    void printGraph() const {
        cout << "图结构：" << endl;
        cout << "节点数量: " << nodeCount << endl;
        cout << "边数量: " << edges.size() << endl;
        cout << "邻接表：" << endl;

        for (int i = 1; i <= nodeCount; ++i) {
            cout << "节点 " << i << " 的邻居: ";
            for (const Edge& edge : adjList[i]) {
                // 避免重复打印无向边
                if (edge.from == i) {
                    cout << edge.to << "(权重:" << edge.weight << ") ";
                }
            }
            cout << endl;
        }
    }
};

// Dijkstra算法实现，返回最短路径和使用的边
pair<vector<int>, unordered_set<int>> dijkstra(const Graph& graph, int start, int end, const unordered_set<int>& forbiddenEdges) {
    int n = graph.getNodeCount();
    const auto& adjList = graph.getAdjList();

    vector<int> dist(n + 1, numeric_limits<int>::max());
    vector<int> prev(n + 1, -1);
    vector<int> edgeUsed(n + 1, -1); // 记录到达每个节点使用的边ID

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        auto current = pq.top();
        pq.pop();
        int u = current.second;
        int currentDist = current.first;

        if (u == end) break;
        if (currentDist > dist[u]) continue;

        for (const Edge& edge : adjList[u]) {
            // 跳过禁止的边
            if (forbiddenEdges.count(edge.id)) continue;

            int v = edge.to;
            int newDist = dist[u] + edge.weight;

            if (newDist < dist[v]) {
                dist[v] = newDist;
                prev[v] = u;
                edgeUsed[v] = edge.id;
                pq.push({newDist, v});
            }
        }
    }

    // 构建路径和使用的边集合
    vector<int> path;
    unordered_set<int> usedEdges;

    if (dist[end] == numeric_limits<int>::max()) {
        return make_pair(path, usedEdges); // 没有路径
    }

    // 从终点回溯路径
    for (int at = end; at != -1; at = prev[at]) {
        path.push_back(at);
        if (prev[at] != -1) {
            usedEdges.insert(edgeUsed[at]);
        }
    }

    reverse(path.begin(), path.end());

    return make_pair(path, usedEdges);
}

// 合并两条路径并计算总长度
pair<vector<int>, int> mergePaths(const vector<int>& path1, const vector<int>& path2, const Graph& graph) {
    vector<int> mergedPath = path1;

    // 合并路径，避免重复添加中间节点
    for (size_t i = 1; i < path2.size(); ++i) {
        mergedPath.push_back(path2[i]);
    }

    // 计算总长度
    int totalLength = 0;
    const auto& adjList = graph.getAdjList();

    // 计算第一段路径长度
    for (size_t i = 0; i < path1.size() - 1; ++i) {
        int u = path1[i];
        int v = path1[i + 1];
        for (const Edge& edge : adjList[u]) {
            if (edge.to == v) {
                totalLength += edge.weight;
                break;
            }
        }
    }

    // 计算第二段路径长度
    for (size_t i = 0; i < path2.size() - 1; ++i) {
        int u = path2[i];
        int v = path2[i + 1];
        for (const Edge& edge : adjList[u]) {
            if (edge.to == v) {
                totalLength += edge.weight;
                break;
            }
        }
    }

    return make_pair(mergedPath, totalLength);
}

// 处理单组测试用例
void processTestCase(int caseNum) {
    int N, M;
    cin >> N >> M;

    Graph graph(N);

    for (int i = 0; i < M; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        graph.addEdge(u, v, w, i); // 使用i作为边的唯一ID
    }

    // 打印图结构
    graph.printGraph();

    // 第一次Dijkstra：从1到N
    cout << "\n开始第一次路径搜索：从起点1到终点" << N << endl;
    auto result1 = dijkstra(graph, 1, N, unordered_set<int>());
    vector<int> path1 = result1.first;
    unordered_set<int> usedEdges = result1.second;

    if (path1.empty()) {
        cout << "测试用例 " << caseNum << ": 无法从1到达" << N << endl;
        return;
    }
    cout << "第一次路径找到: ";
    for (size_t i = 0; i < path1.size(); ++i) {
        if (i != 0) cout << " -> ";
        cout << path1[i];
    }
    cout << endl;

    // 第二次Dijkstra：从N到1，避开已经使用的边
    cout << "\n开始第二次路径搜索：从终点" << N << "返回起点1" << endl;
    auto result2 = dijkstra(graph, N, 1, usedEdges);
    vector<int> path2 = result2.first;

    if (path2.empty()) {
        cout << "测试用例 " << caseNum << ": 无法从" << N << "返回1" << endl;
        return;
    }
    cout << "第二次路径找到: ";
    for (size_t i = 0; i < path2.size(); ++i) {
        if (i != 0) cout << " -> ";
        cout << path2[i];
    }
    cout << endl;

    // 合并路径
    auto finalResult = mergePaths(path1, path2, graph);
    vector<int> finalPath = finalResult.first;
    int totalLength = finalResult.second;

    // 输出结果 - 格式化为方便GUI解析的形式
    cout << "\n测试用例 " << caseNum << " 结果:" << endl;
    cout << "完整路径: ";
    for (size_t i = 0; i < finalPath.size(); ++i) {
        if (i != 0) cout << " -> ";
        cout << finalPath[i];
    }
    cout << endl;
    cout << "路径总长度: " << totalLength << endl;

    // 为了便于GUI可视化，可以额外输出路径详情
    cout << "路径详情: [";
    for (size_t i = 0; i < finalPath.size(); ++i) {
        if (i != 0) cout << ",";
        cout << finalPath[i];
    }
    cout << "]" << endl;

    // 输出边详情，便于GUI高亮显示
    cout << "边详情：[";
    bool firstEdge = true;
    for (size_t i = 0; i < finalPath.size() - 1; ++i) {
        int u = finalPath[i];
        int v = finalPath[i + 1];
        const auto& adjList = graph.getAdjList();
        for (const Edge& edge : adjList[u]) {
            if (edge.to == v) {
                if (!firstEdge) cout << ",";
                cout << "(" << edge.from << "-" << edge.to << ")";
                firstEdge = false;
                break;
            }
        }
    }
    cout << "]" << endl;
}

int main() {

    int T;
    cout << "请输入测试用例数量: ";
    cin >> T;

    for (int i = 1; i <= T; ++i) {
        cout << "\n=== 处理测试用例 " << i << " ===" << endl;
        cout << "请输入节点数量和边数量 (格式: N M): ";
        processTestCase(i);
    }

    return 0;
}